package test3.backtracking;

public class Exist {
    private int col;
    private int row;
    private char[] letters;
    private int width;
    private boolean[][] b;
    private char[][] board;


    public static void main(String[] args) {
        char[][] board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        String word = "SEE";
        Exist exist = new Exist();
        boolean b = exist.exist(board, word);
        System.out.println(b);
    }

    public boolean exist(char[][] board, String word) {
        this.row = board.length;
        this.col = board[0].length;
        this.letters = word.toCharArray();
        this.width = letters.length;
        this.board = board;
        this.b = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (exist(i, j, 0)) return true;
            }
        }

        return false;
    }

    private boolean exist(int i, int j, int index) {

        if (index >= width) return true;
        if (i < 0 || i >= row || j < 0 || j >= col || letters[index] != board[i][j] || b[i][j]) return false;

        b[i][j] = true;
        boolean res = exist(i + 1, j, index + 1) || exist(i, j + 1, index + 1)
                || exist(i - 1, j, index + 1) || exist(i, j - 1, index + 1);
        b[i][j] = false;
        return res;
    }
}
